package org.example;

public class Test2 {
    //letcode 完全平方数
    //https://leetcode.cn/problems/perfect-squares/description/?envType=problem-list-v2&envId=dynamic-programming&difficulty=MEDIUM

    /**
     * 问题可以看成是从1，4，9..等数中挑选，使得构成和为n的最少的数，所以就可以当成背包问题，而一个元素可以被选多次
     * //所以就是完全背包问题
     * @param n
     * @return
     */
    public int numSquares(int n) {
        int aim = (int) Math.sqrt(n);
        int[][] dp = new int[aim + 1][n + 1];
        int INF = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++) dp[0][i] = INF;
        for (int i = 1; i <= aim; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= i * i) {
                    dp[i][j] = Math.min(dp[i][j],dp[i][j-i*i] + 1);
                }
            }
        }
        return dp[aim][n];
    }

    /**
     * 优化
     * @param n
     * @return
     */
    public int numSquares2(int n) {
        int aim = (int) Math.sqrt(n);
        int[] dp = new int[n + 1];
        int INF = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++) dp[i] = INF;
        for (int i = 1; i <= aim; i++) {
            for (int j = i*i; j <= n; j++) {
                dp[j] = Math.min(dp[j],dp[j-i*i] + 1);
            }
        }
        return dp[n];
    }
}
